package leetcode.biweekly.week86;

import java.util.PriorityQueue;

//Solution4Test
public class Solution4 {
	int[] chargeTimes, runningCosts;
	long budget;
	int n;

	public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
		this.chargeTimes = chargeTimes;
		this.runningCosts = runningCosts;
		this.budget = budget;
		this.n = chargeTimes.length;
		int l = 1, r = n;
		int ans = 0;
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			boolean ok = this.check(mid);
			if (ok) {
				ans = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return ans;
	}

	private boolean check(int size) {
		int p = 0;
		long sum = 0;
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[0] - a[0]);
		while (p < size) {
			sum += this.runningCosts[p];
			queue.add(new int[] { this.chargeTimes[p], p });
			p++;
		}
		int ans = 0;
		if (this.cost(queue.peek()[0], size, sum) <= this.budget) {
			return true;
		}
		while (p < this.n) {
			int out = p - size;
			sum += this.runningCosts[p] - this.runningCosts[out];
			while (!queue.isEmpty() && queue.peek()[1] <= out) {
				queue.poll();
			}
			queue.add(new int[] { this.chargeTimes[p], p });
			if (this.cost(queue.peek()[0], size, sum) <= this.budget) {
				return true;
			}
			p++;
		}
		return false;
	}

	private long cost(long max, long size, long sum) {
//		System.out.println(max +" " + size + " " + sum);
		return max + size * sum;
	}

}
